package com.platform.modules.alg.alglib.poj1986;

public class Poj1986A {
    public String output = "";
    private int N = 100005;
    int n; // 节点数
    int m; // 边数
    int q; //  查询数
    int top;
    int c[][] = new int[N][2]; // 节点的左右还在
    int fa[] = new int[N]; // 节点的父亲
    int v[] = new int[N]; // 节点的权值
    int dis[] = new int[N];
    int st[] = new int[N];
    int rev[] = new int[N];

    public String cal(String input) {
        int x, y, w;
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[1]);

        for (int i = 1; i <= m; i++) {
            String[] info = line[i].split(" ");
            x = Integer.parseInt(info[0]);
            y = Integer.parseInt(info[1]);
            w = Integer.parseInt(info[2]);
            v[n + i] = w;
            link(x, n + i);
            link(n + i, y);
        }
        q = Integer.parseInt(line[m + 1]);
        int count = 2;
        while (q-- > 0) {
            String[] query = line[m + count++].split(" ");
            x = Integer.parseInt(query[0]);
            y = Integer.parseInt(query[1]);
            if (x == y) {
                output += "0\n";
                continue;
            }
            split(x, y);
            output += dis[y] + "\n";
        }
        return output;
    }

    void update(int x) {
        dis[x] = dis[c[x][0]] + dis[c[x][1]] + v[x];
    }

    void pushdown(int x) {
        int l = c[x][0], r = c[x][1];
        if (rev[x] == 1) {
            rev[l] ^= 1;
            rev[r] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
    }

    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y];
        int k;
        if (c[y][0] == x) {
            k = 1;
        } else {
            k = 0;
        }

        if (!isroot(y)) c[z][c[z][1] == y ? 1 : 0] = x;
        fa[x] = z;
        fa[y] = x;
        fa[c[x][k]] = y;
        c[y][k == 0 ? 1 : 0] = c[x][k];
        c[x][k] = y;
        update(y);
        update(x);
    }

    void splay(int x) {
        top = 0;
        st[++top] = x;
        for (int i = x; !isroot(i); i = fa[i])
            st[++top] = fa[i];
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }

    void access(int x) {
        for (int t = 0; x > 0; t = x, x = fa[x]) {
            splay(x);
            c[x][1] = t;
            update(x);
        }
    }

    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }

    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }

    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }

    void cut(int x, int y) {
        split(x, y);
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }

    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }

}
